/*
 * @lc app=leetcode.cn id=149 lang=cpp
 *
 * [149] 直线上最多的点数
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int num = points.size();
        if (num < 3){return num;}

        int res = 0;
        for (int i=0;i<num;++i){
            unordered_map<double, int> hashTable;
            int infinit = 0;
            int uninfinit = 0;

            for (int j=i+1;j<num;++j){
                if (points[i][0] == points[j][0]){
                    if (infinit == 0){
                        infinit = 2;
                    }else{
                        infinit++;
                    }
                }else{
                    double k = double(points[i][1] - points[j][1])/
                               double(points[i][0] - points[j][0]);
                    auto iterFind = hashTable.find(k);
                    if (iterFind != hashTable.end()){
                        iterFind->second += 1;
                    }else{
                        hashTable.emplace(k, 2);
                    }                     
                }
            }
            for (auto& line : hashTable){
                if (line.second > uninfinit){
                    uninfinit = line.second;
                }
            }
            // get max for this point
            int currentMax = max(infinit, uninfinit);
            if (currentMax > res){res = currentMax;}            
        }
        return res;
    }
};
// @lc code=end

// [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
int main(){
    vector<vector<int>> myTest
    {{54,153},{1,3},{0,-72},{-3,3},{12,-22},{-60,-322},{0,-5},{-5,1},{5,5},{36,78},{3,-4},{5,0},{0,4},{-30,-197},{-5,0},{60,178},{0,0},{30,53},{24,28},{4,5},{2,-2},{-18,-147},{-24,-172},{-36,-222},{-42,-247},{2,3},{-12,-122},{-54,-297},{6,-47},{-5,3},{-48,-272},{-4,-2},{3,-2},{0,2},{48,128},{4,3},{2,4}};
    // {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
    Solution mySolution;
    int res = mySolution.maxPoints(myTest);
    printf("check res %d\n", res);
    return 0;
}

class Solution2 {
public:
    // hashfunc
struct hashfunc
{
    template<typename T, typename U>
    size_t operator() (const pair<T, U> &i) const
    {
        return hash<T>()(i.first) ^ hash<U>()(i.second);
    }
};
using KEY = pair<int, int>;
struct PairEqualTo
{
    bool operator()(const KEY& p1,const KEY& p2) const noexcept
    {
        // printf("wtf f %d %d s %d %d res %d\n", p1.first, p2.first, p1.second, p2.second, p1.first == p2.first && p1.second == p2.second);
        return p1.first == p2.first && p1.second == p2.second;
    }
};
// unordered_map< pair<int, int>, int , hashfunc > mp;
    int maxPoints(vector<vector<int>>& points) {
        typedef std::vector<int> V;
        using P = pair<int, int>;
        unordered_map<P, int, hashfunc, PairEqualTo> hashLine;
        // key : <k, b> : y = k*x + b
        // value : count of points belonging to this line
        // 哈希不支持pair， 自己做一个仿函数
        // hashLine.bucket_count();

        for (int i=0;i<points.size()-1;++i){
            for (int j=i+1;j<points.size();++j){
                double k, b;
                // 注意转换类型，自带的隐式类型转换发生在除号之后妈的全变成0了
                if (points[j][0]==points[i][0]) {
                    k = 9999.9999;
                    b = points[j][0];
                }else{
                    k = double(points[j][1]-points[i][1])/double(points[j][0]-points[i][0]);
                    b = points[i][1] - k * points[i][0];
                }
                
                k *= 100000;
                b *= 100000;
                // INT32_MAX;

                int k_ = static_cast<int>(k);
                int b_ = static_cast<int>(b);

                P lineKey = {k_, b_};
                if (hashLine.find(lineKey) != hashLine.end()){
                    hashLine[lineKey] += 1;
                    printf("add %d %d %d %d num %d (y %d, x %d)\n", lineKey.first, lineKey.second, i, j, hashLine[lineKey], points[j][1]-points[i][1], points[j][0]-points[i][0]);
                }else{
                    hashLine.emplace(lineKey, 1);
                    printf("new %d %d %d %d num %d (y %d, x %d)\n", lineKey.first, lineKey.second, i, j, hashLine[lineKey], points[j][1]-points[i][1], points[j][0]-points[i][0]);
                }
            }
        }

        int max = 0;
        for (auto& item : hashLine){
            if (item.second > max){
                max = item.second;
            }
        }
        printf("check max %d\n", max);
        int res = static_cast<int>((1+sqrt(1+8*max))/2);
        return res;
    }
};
